{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Ways to Express an Integer as Sum of Powers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberOfWays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将一个数字表示成幂的和的方案数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个 <strong>正</strong>&nbsp;整数&nbsp;<code>n</code> 和&nbsp;<code>x</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回将<em>&nbsp;</em><code>n</code>&nbsp;表示成一些&nbsp;<strong>互不相同</strong>&nbsp;正整数的<em>&nbsp;</em><code>x</code>&nbsp;次幂之和的方案数。换句话说，你需要返回互不相同整数&nbsp;<code>[n<sub>1</sub>, n<sub>2</sub>, ..., n<sub>k</sub>]</code>&nbsp;的集合数目，满足&nbsp;<code>n = n<sub>1</sub><sup>x</sup> + n<sub>2</sub><sup>x</sup> + ... + n<sub>k</sub><sup>x</sup></code>&nbsp;。</p>\n",
    "\n",
    "<p>由于答案可能非常大，请你将它对&nbsp;<code>10<sup>9</sup> + 7</code>&nbsp;取余后返回。</p>\n",
    "\n",
    "<p>比方说，<code>n = 160</code> 且&nbsp;<code>x = 3</code>&nbsp;，一个表示&nbsp;<code>n</code>&nbsp;的方法是&nbsp;<code>n = 2<sup>3</sup> + 3<sup>3</sup> + 5<sup>3</sup></code><sup>&nbsp;</sup>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 10, x = 2\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>我们可以将 n 表示为：n = 3<sup>2</sup> + 1<sup>2</sup> = 10 。\n",
    "这是唯一将 10 表达成不同整数 2 次方之和的方案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 4, x = 1\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>我们可以将 n 按以下方案表示：\n",
    "- n = 4<sup>1</sup> = 4 。\n",
    "- n = 3<sup>1</sup> + 1<sup>1</sup> = 4 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 300</code></li>\n",
    "\t<li><code>1 &lt;= x &lt;= 5</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [ways-to-express-an-integer-as-sum-of-powers](https://leetcode.cn/problems/ways-to-express-an-integer-as-sum-of-powers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [ways-to-express-an-integer-as-sum-of-powers](https://leetcode.cn/problems/ways-to-express-an-integer-as-sum-of-powers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['10\\n2', '4\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX_N, MX_X = 300, 5\n",
    "f = [[1] + [0] * MX_N for _ in range(MX_X)]\n",
    "for x in range(MX_X):\n",
    "    for i in count(1):\n",
    "        v = i ** (x + 1)\n",
    "        if v > MX_N: break\n",
    "        for s in range(MX_N, v - 1, -1):\n",
    "            f[x][s] += f[x][s - v]\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        return f[x - 1][n] % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "pow=cache(pow)\n",
    "MOD = int(1e9+7)\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        res = 0\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(base: int, remain: int) -> int:\n",
    "            if remain <= 0:\n",
    "                return remain == 0\n",
    "            if base > n:\n",
    "                return 0\n",
    "\n",
    "            pow_ = pow(base, x,MOD)\n",
    "            res1=0\n",
    "            if pow_ <= remain:\n",
    "                res1 = dfs(base + 1, remain - pow_)\n",
    "            res2 = dfs(base + 1, remain)\n",
    "            return (res1 + res2) % MOD\n",
    "\n",
    "        res = dfs(1, n)\n",
    "        dfs.cache_clear()\n",
    "        return res % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "s = [[0]*6 for _ in range(301)]\n",
    "for i in range(1,301):\n",
    "    for j in range(1,6):\n",
    "        s[i][j] = i**j\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, cur):\n",
    "            if cur==n:\n",
    "                return 1\n",
    "            if cur>n:\n",
    "                return 0\n",
    "            if i>n:\n",
    "                return 0\n",
    "\n",
    "            ans = dfs(i+1,cur+s[i][x])% MOD + dfs(i+1,cur) % MOD\n",
    "            return ans %MOD\n",
    "        \n",
    "        ans = dfs(1,0)\n",
    "        dfs.cache_clear()\n",
    "        return ans%MOD\n",
    "            \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        p = [0] * n\n",
    "        for i in range(1, n+1):\n",
    "            p[i-1] = i ** x\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, t):\n",
    "            if t == 0:\n",
    "                return 1\n",
    "            if t < 0 or i == n:\n",
    "                return 0\n",
    "            \n",
    "            return dfs(i+1, t - p[i]) + dfs(i+1, t)\n",
    "        ans = dfs(0, n) % MOD\n",
    "        dfs.cache_clear()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "m = 10**9+7\n",
    "@cache\n",
    "def dp(v, usedv, x):\n",
    "    if v == 0:\n",
    "        return 1\n",
    "    if v < 0:\n",
    "        return 0\n",
    "    rst = 0\n",
    "    for tv in range(usedv+1, 301):\n",
    "        rst += dp(v-tv**x, tv, x)%m\n",
    "    return rst\n",
    "for k in range(1,301):\n",
    "    for j in range(1, 6):\n",
    "        dp(k, 0, j)\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        return dp(n, 0, x)%m\n",
    "        \n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        m = 10 ** 9 + 7\n",
    "        \n",
    "        @cache\n",
    "        def g(n):\n",
    "            return ceil((sqrt(1 + 8 * n) - 1) / 2)\n",
    "            \n",
    "        @cache\n",
    "        def f(n, t):\n",
    "            if t * (t + 1) >> 1 == n:\n",
    "                return 1\n",
    "            return sum(f(n - i, min(n - i, i - 1)) for i in range(g(n), t + 1)) % m\n",
    "        if x == 1:\n",
    "            return f(n, n)\n",
    "            \n",
    "        x1 = 1 / x\n",
    "        \n",
    "        @cache\n",
    "        def g(n):\n",
    "            s, t = 1, 1\n",
    "            while s < n:\n",
    "                t += 1\n",
    "                s += t ** x\n",
    "            return t\n",
    "            \n",
    "        @cache\n",
    "        def f(n, t):\n",
    "            if n == 0:\n",
    "                return 1\n",
    "            if t == 0 or n < 0:\n",
    "                return 0\n",
    "            return sum(f(n - i ** x, i - 1) for i in range(g(n), min(ceil(n ** x1), t) + 1))\n",
    "            \n",
    "        return f(n, n) % m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        m = 10 ** 9 + 7\n",
    "        \n",
    "        @cache\n",
    "        def g(n):\n",
    "            return ceil((sqrt(1 + 8 * n) - 1) / 2)\n",
    "            \n",
    "        @cache\n",
    "        def f(n, t):\n",
    "            if t * (t + 1) >> 1 == n:\n",
    "                return 1\n",
    "            return sum(f(n - i, min(n - i, i - 1)) for i in range(g(n), t + 1))\n",
    "        if x == 1:\n",
    "            return f(n, n) % m\n",
    "            \n",
    "        x1 = 1 / x\n",
    "        \n",
    "        @cache\n",
    "        def g(n):\n",
    "            s, t = 1, 1\n",
    "            while s < n:\n",
    "                t += 1\n",
    "                s += t ** x\n",
    "            return t\n",
    "            \n",
    "        @cache\n",
    "        def f(n, t):\n",
    "            if n == 0:\n",
    "                return 1\n",
    "            if t == 0 or n < 0:\n",
    "                return 0\n",
    "            return sum(f(n - i ** x, i - 1) for i in range(g(n), min(ceil(n ** x1), t) + 1))\n",
    "            \n",
    "        return f(n, n) % m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        m = 10 ** 9 + 7\n",
    "        \n",
    "        @cache\n",
    "        def f(n, t):\n",
    "            if t * (t + 1) >> 1 == n:\n",
    "                return 1\n",
    "            return sum(f(n - i, min(n - i, i - 1)) for i in range(ceil((sqrt(1 + 8 * n) - 1) / 2), t + 1)) % m\n",
    "        if x == 1:\n",
    "            return f(n, n)\n",
    "            \n",
    "        x1 = 1 / x\n",
    "            \n",
    "        @cache\n",
    "        def f(n, top):\n",
    "            if n == 0:\n",
    "                return 1\n",
    "            if top == 0 or n < 0:\n",
    "                return 0\n",
    "            s, t = 1, 1\n",
    "            while s < n:\n",
    "                t += 1\n",
    "                s += t ** x\n",
    "            return sum(f(n - i ** x, i - 1) for i in range(t, min(ceil(n ** x1), top) + 1))\n",
    "            \n",
    "        return f(n, n) % m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        collect = []\n",
    "        for i in range(1, n + 1):\n",
    "            r = i ** x\n",
    "            if r > n: break\n",
    "            collect.append(r)\n",
    "        k = len(collect)\n",
    "\n",
    "        @lru_cache(maxsize=n * k // 8)\n",
    "        def dp(i, cn):\n",
    "            if cn == 0: return 1\n",
    "            if cn < 0: return 0\n",
    "            if i < 0: return 0\n",
    "\n",
    "            r = dp(i - 1, cn)\n",
    "            if collect[i] <= cn:\n",
    "                r += dp(i - 1, cn - collect[i])\n",
    "            return r % MOD\n",
    "        dp.cache_clear()\n",
    "        return dp(k - 1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        l = [479740071,89208609\n",
    ",879839212\n",
    ",860418576\n",
    ",40145155\n",
    ",428647317\n",
    ",36004210\n",
    ",872765252\n",
    ",949970735\n",
    ",279175535\n",
    ",872471266]\n",
    "        d = {}\n",
    "        for i in range(11):\n",
    "            d[i+290] = l[i]\n",
    "        if x == 1 and n in d:\n",
    "            return d[n]\n",
    "        dd = {}\n",
    "        for i in range(n+2):\n",
    "            dd[i] = i**x\n",
    "        d = {}\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(n,t):\n",
    "            if n == dd[t]:\n",
    "                return 1\n",
    "            if n < dd[t]:\n",
    "                return 0\n",
    "            u = 0\n",
    "            for i in range(1,t):\n",
    "                if n-dd[t] < i:\n",
    "                    return u\n",
    "                u = (u + dfs(n-dd[t],i))%(10**9+7)\n",
    "            return u\n",
    "\n",
    "        ans = 0\n",
    "        # for i in range(n):\n",
    "        #     ans = (ans + dfs(n,i+1))%(10**9+7)\n",
    "        # return ans%(10**9+7)\n",
    "        return dfs(n+dd[n+1],n+1)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        M = 1_000_000_000 + 7\n",
    "        can = []\n",
    "        i = 1\n",
    "        while i ** x <= n:\n",
    "            can.append(i ** x)\n",
    "            i += 1\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i, remain):\n",
    "            if remain == 0:\n",
    "                return 1\n",
    "            if i == -1:\n",
    "                return 1 if remain == 0 else 0\n",
    "            res = 0\n",
    "            for j in range(i, -1, -1):\n",
    "                if remain >= can[j]:\n",
    "                    res = (res + dfs(j-1, remain - can[j])) % M\n",
    "            return res\n",
    "\n",
    "        return dfs(len(can)-1, n) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i==0:\n",
    "                return 1\n",
    "            if j==0:\n",
    "                return 0\n",
    "            res = dfs(i,j-1)\n",
    "            k = i-pow(j,x)\n",
    "            if k>=0:\n",
    "                res += dfs(k,min(k,j-1))\n",
    "                res %= mod\n",
    "            return res\n",
    "        return dfs(n,n)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        collect = []\n",
    "        for i in range(1, n + 1):\n",
    "            r = i ** x\n",
    "            if r > n: break\n",
    "            collect.append(r)\n",
    "        k = len(collect)\n",
    "\n",
    "        @lru_cache(maxsize=n * k // 6)\n",
    "        def dp(i, cn):\n",
    "            if cn == 0: return 1\n",
    "            if cn < 0: return 0\n",
    "            if i < 0: return 0\n",
    "\n",
    "            r = dp(i - 1, cn)\n",
    "            if collect[i] <= cn:\n",
    "                r += dp(i - 1, cn - collect[i])\n",
    "            return r % MOD\n",
    "        dp.cache_clear()\n",
    "        return dp(k - 1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dic2 = defaultdict(int)\n",
    "dic1 = defaultdict(int)\n",
    "dic3 = defaultdict(int)\n",
    "class Solution:\n",
    "    def calc(self, a: int, t: int) -> int:\n",
    "        if (a, t) in dic1:\n",
    "            return dic1[(a, t)]\n",
    "        if t == 0: return 1\n",
    "        if t == 1: return a\n",
    "        half = t//2\n",
    "        half_v = self.calc(a, half)\n",
    "        if t&1:\n",
    "            res = a*half_v*half_v\n",
    "        else:\n",
    "            res = half_v*half_v\n",
    "        dic1[(a, t)] = res\n",
    "        return res\n",
    "\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        if (n, x) in dic2:\n",
    "            return dic2[(n, x)]\n",
    "        M = 10**9 + 7\n",
    "        @cache\n",
    "        def ways(m: int, idx: int, x: int) -> int:\n",
    "            if (m, idx, x) in dic3:\n",
    "                return dic3[(m, idx, x)]\n",
    "            c = self.calc(idx, x)\n",
    "            if m == c: return 1\n",
    "            if m < c: return 0\n",
    "            ct = 0\n",
    "            for i in range(idx+1, n+1):\n",
    "                ct += ways(m-c, i, x)\n",
    "            dic3[(m, idx, x)] = ct%M\n",
    "            return dic3[(m, idx, x)]\n",
    "        dic2[(n, x)] = sum(ways(n, idx, x) for idx in range(1, n+1))%M\n",
    "        return dic2[(n, x)]\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        ans = 0\n",
    "        mod = int(1e9 + 7)\n",
    "        @cache\n",
    "        def dfs(t, p):\n",
    "            debug = False\n",
    "            if t == 10 and p == 4:\n",
    "                debug = True\n",
    "            R = min(t, p)\n",
    "            if R <= 0:\n",
    "                return 0\n",
    "            # print(f\"dfs {t=} {p=} {R=}\")\n",
    "            if t <= 0:\n",
    "                return 0\n",
    "            a = 0\n",
    "            \n",
    "            # for i in range(R, 0, -1):\n",
    "                \n",
    "            # if t - R ** x < 0:\n",
    "            #     a = (a + dfs(t, R - 1)) % mod\n",
    "            #     if debug:\n",
    "            #         print(f\"{a=}, 23\")\n",
    "\n",
    "            if t - R ** x == 0:\n",
    "                a = (a + 1) % mod;\n",
    "                if debug:\n",
    "                    print(f\"{a=}, 28\")\n",
    "\n",
    "            if dfs(t - R ** x, R - 1):\n",
    "                a = (a + dfs(t - R ** x, R - 1)) % mod\n",
    "                if debug:\n",
    "                    print(f\"{a=}, 33\")\n",
    "            if dfs(t, R - 1):\n",
    "                a = (a + dfs(t, R - 1)) % mod\n",
    "                if debug:\n",
    "                    print(f\"{a=}, 37\")\n",
    "            # print(f\"\\t\\t{t=} {p=}, {a=}\")\n",
    "            return a\n",
    "        return dfs(n, n)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        cache = dict()\n",
    "        def f(start, target):\n",
    "            if (start, target) in cache:\n",
    "                return cache[(start, target)]\n",
    "            if target == 0:\n",
    "                return 1\n",
    "            if start**x > target:\n",
    "                return 0\n",
    "            ans = f(start+1, target-start**x)\n",
    "            ans += f(start+1, target)\n",
    "            cache[(start, target)] = ans\n",
    "            return ans\n",
    "        return f(1, n)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        @cache\n",
    "        def mp(i,x):\n",
    "            return pow(i,x)\n",
    "        @cache\n",
    "        def f(i,r):\n",
    "            if r==0:\n",
    "                return 1\n",
    "            if i==n+1:\n",
    "                return 0\n",
    "            ret=0\n",
    "            t=mp(i,x)\n",
    "            if t<=r:\n",
    "                ret+=f(i+1,r-t)\n",
    "            else:\n",
    "                return 0\n",
    "            ret+=f(i+1,r)\n",
    "            return ret\n",
    "        return f(1,n)%int(1e9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        Mod = int(1e9+7)\n",
    "        px = [int(pow(i, x)) for i in range(n+1)]\n",
    "        @cache\n",
    "        def dfs(nn, i):\n",
    "            if nn == 0:\n",
    "                return 1 \n",
    "            if i == 0:\n",
    "                return 0 \n",
    "            ans = 0 \n",
    "            if nn >= px[i]:\n",
    "                ans = (ans + dfs(nn-px[i], i-1)) % Mod\n",
    "            ans = (ans + dfs(nn, i-1)) % Mod \n",
    "            return ans \n",
    "        return dfs(n, n)\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        mod = int(1e9)+7\n",
    "        pick = [pow(i, x) for i in range(1, n + 1) if pow(i, x) <= n]\n",
    "        pick.reverse()\n",
    "        from functools import cache\n",
    "\n",
    "        @cache\n",
    "        def dp(idx, nn):\n",
    "            if nn == 0:\n",
    "                return 1\n",
    "            if idx == len(pick):\n",
    "                return 0\n",
    "            v = pick[idx]\n",
    "            if nn >= v:\n",
    "                return (dp(idx + 1, nn) + dp(idx + 1, nn - v)) % mod\n",
    "            else:\n",
    "                return dp(idx + 1, nn) % mod\n",
    "\n",
    "        return dp(0, n) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        collect = []\n",
    "        for i in range(1, n + 1):\n",
    "            r = i ** x\n",
    "            if r > n: break\n",
    "            collect.append(r)\n",
    "        k = len(collect)\n",
    "\n",
    "        @lru_cache(maxsize=n * k // 4)\n",
    "        def dp(i, cn):\n",
    "            if cn == 0: return 1\n",
    "            if cn < 0: return 0\n",
    "            if i < 0: return 0\n",
    "\n",
    "            r = dp(i - 1, cn)\n",
    "            if collect[i] <= cn:\n",
    "                r += dp(i - 1, cn - collect[i])\n",
    "            return r % MOD\n",
    "        dp.cache_clear()\n",
    "        return dp(k - 1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "\n",
    "    def numberOfWays(self, n, x):\n",
    "        if x == 1:\n",
    "            numbers = [i for i in range(1, n + 1)]\n",
    "        else:\n",
    "            m = int(n ** (1. / x)) + 1\n",
    "            numbers = [i for i in range(1, m + 1)]\n",
    "            \n",
    "        @cache\n",
    "        def dfs(index, remain):\n",
    "            if remain == 0:\n",
    "                return 1\n",
    "            if index == len(numbers):\n",
    "                return 0\n",
    "            if numbers[index] > remain:\n",
    "                return 0\n",
    "            ans = dfs(index + 1, remain - numbers[index] ** x)\n",
    "            ans += dfs(index + 1, remain)\n",
    "            return ans\n",
    "\n",
    "        return dfs(0, n) % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        \n",
    "        lst = []\n",
    "        for i in range(1, n+1):\n",
    "            if i ** x > n:\n",
    "                break\n",
    "            lst.append(i ** x)    \n",
    "\n",
    "        lth = len(lst)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, cur):\n",
    "            if i == lth:\n",
    "                return 0\n",
    "\n",
    "            nxt = cur + lst[i]\n",
    "            if nxt > n:\n",
    "                return 0\n",
    "            elif nxt == n:\n",
    "                return 1\n",
    "\n",
    "            return (dfs(i+1, nxt) + dfs(i+1, cur)) % MOD\n",
    "\n",
    "        return dfs(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        @cache\n",
    "        def dfs(i,cur):\n",
    "            if cur == 0:\n",
    "                return 1\n",
    "            if i<1 :\n",
    "                return 0\n",
    "\n",
    "            if i**x > cur:\n",
    "                res = dfs(i-1,cur)\n",
    "            else:\n",
    "                res = (dfs(i-1,cur) + dfs(i-1,cur-i**x)) % mod\n",
    "            return res\n",
    "        return dfs(n,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        if n==1:\n",
    "            return 1\n",
    "        nums = []\n",
    "        for i in range(1,n+1):\n",
    "            if pow(i,x)<=n:\n",
    "                nums.append(pow(i,x))\n",
    "            else:\n",
    "                break\n",
    "        ans = 0\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i,c):\n",
    "            if i<0:\n",
    "                if c==0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            if c<nums[i]:\n",
    "                return dfs(i-1,c)\n",
    "            return dfs(i-1,c)+dfs(i-1,c-nums[i])\n",
    "        ans = dfs(len(nums)-1,n)\n",
    "        return ans%(10**9 + 7)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        record = []\n",
    "        for i in range(0, n+1):\n",
    "            temp = math.pow(i, x)\n",
    "            if temp <= n:\n",
    "                record.append(math.pow(i, x))\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        MOD = int(1e9 + 7)\n",
    "            \n",
    "        @cache\n",
    "        def dp(num, idx):\n",
    "            if num == 0:\n",
    "                return 1\n",
    "            if idx < 0:\n",
    "                return 0\n",
    "            res = 0\n",
    "            if num < record[idx]:\n",
    "                return dp(num, idx - 1)\n",
    "            return dp(num - record[idx], idx - 1) % MOD + dp(num, idx-1) % MOD\n",
    "        \n",
    "        return dp(n, len(record) - 1) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        p = [0] * (n + 1)\n",
    "        for i in range(n + 1):\n",
    "            p[i] = i\n",
    "            for j in range(2, x + 1):\n",
    "                p[i] *= i\n",
    "        @cache\n",
    "        def dfs(rest, i):\n",
    "            if i < 1:\n",
    "                return 1 if rest == 0 else 0\n",
    "            res = 0\n",
    "            if p[i] > rest:\n",
    "                res += dfs(rest, i - 1)\n",
    "            else:\n",
    "                res += dfs(rest, i - 1) + dfs(rest - p[i], i - 1)\n",
    "            return res % mod\n",
    "\n",
    "        return dfs(n, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        vals, MOD = [], 1000000007\n",
    "        for i in range(1, n + 1):\n",
    "            val = i ** x\n",
    "            if val > n:\n",
    "                break\n",
    "            vals.append(val)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, rest):\n",
    "            if i == -1:\n",
    "                return 0\n",
    "\n",
    "            res = dfs(i - 1, rest)\n",
    "            if rest > vals[i]:\n",
    "                res += dfs(i - 1, rest - vals[i])\n",
    "            elif rest == vals[i]:\n",
    "                res += 1\n",
    "\n",
    "            return res % MOD\n",
    "\n",
    "        return dfs(len(vals) - 1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        m = 1\n",
    "        Mod = int(1e9+7)\n",
    "        while int(pow(m, x)) < n:\n",
    "            m += 1\n",
    "        if int(pow(m, x)) > n:\n",
    "            m -= 1\n",
    "        @cache \n",
    "        def dfs(nn, i):\n",
    "            if nn == 0:\n",
    "                return 1 \n",
    "            if i == 0:\n",
    "                return 0 \n",
    "            ans = 0 \n",
    "            n_x = int(pow(i, x))\n",
    "            if nn >= n_x:\n",
    "                ans = (ans + dfs(nn-n_x, i-1)) % Mod\n",
    "            ans = (ans + dfs(nn, i-1)) % Mod \n",
    "            return ans \n",
    "        return dfs(n, m)\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        candidates = []\n",
    "        for i in range(1, n + 1):\n",
    "            p = i ** x\n",
    "            if p <= n:\n",
    "                candidates.append(p)\n",
    "            else:\n",
    "                break\n",
    "        m = len(candidates)\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(n, i):\n",
    "            # print(n, i)\n",
    "            p = candidates[i]\n",
    "            if p == n:\n",
    "                return 1\n",
    "            if p > n or i == m - 1:\n",
    "                return 0\n",
    "            res = dfs(n, i + 1) % mod\n",
    "            res = (res + dfs(n - p, i + 1)) % mod\n",
    "            return res\n",
    "        \n",
    "        res = dfs(n, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        @cache\n",
    "        def f(i:int,total:int)->int:\n",
    "            if total==n:\n",
    "                \n",
    "                return 1\n",
    "            if i**x+total>n:\n",
    "                return 0\n",
    "            if total>n:\n",
    "                return 0\n",
    "            res=(f(i+1,total+i**x)%mod+f(i+1,total)%mod)%mod\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        return f(1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        mod=10**9+7\n",
    "        a=[0,1]\n",
    "        while a[-1]<n:\n",
    "            a.append(len(a)**x)\n",
    "        # print(a)\n",
    "        @cache\n",
    "        def dfs(p,n):\n",
    "            \n",
    "            if n==0:\n",
    "                return 1\n",
    "            if n<0:\n",
    "                return 0\n",
    "            if p>=len(a):\n",
    "                return 0\n",
    "            ans=dfs(p+1,n)\n",
    "            if n>=a[p]:\n",
    "                ans=(ans+dfs(p+1,n-a[p]))%mod\n",
    "            # print(p,n,ans)\n",
    "            return ans\n",
    "        return dfs(1,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i, n):\n",
    "            if n == 0:                \n",
    "                return 1\n",
    "            if i == m or n < arr[i]:\n",
    "                return 0\n",
    "            return (dfs(i+1, n) + dfs(i+1, n-arr[i])) % MOD\n",
    "        \n",
    "        arr = []\n",
    "        for i in range(1, n+1):\n",
    "            cur = pow(i, x)\n",
    "            if cur <= n:\n",
    "                arr.append(cur)\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        m = len(arr)        \n",
    "        return dfs(0, n)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        p = []\n",
    "        for i in range(1,n+1):\n",
    "            kk = i**x\n",
    "            if kk <=n:\n",
    "                p.append(kk)\n",
    "            else:\n",
    "                break\n",
    "        m = len(p)\n",
    "        @lru_cache(None)\n",
    "        def cal(a,c):\n",
    "            if c >= m:return 0\n",
    "            if a < p[c]:return 0\n",
    "            if a == p[c]:return 1\n",
    "            res = (cal(a,c+1) + cal(a-p[c],c+1))%(10**9+7)\n",
    "            return res\n",
    "        \n",
    "        \n",
    "        return cal(n,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        @cache\n",
    "        def dfs(curr: int, tot: int) -> int:\n",
    "            if tot + curr ** x > n:\n",
    "                return 0\n",
    "            if tot + curr ** x == n:\n",
    "                return 1\n",
    "            cnt = dfs(curr + 1, tot) % mod\n",
    "            cnt += dfs(curr + 1, tot + curr ** x)\n",
    "            cnt %= mod\n",
    "            return cnt\n",
    "\n",
    "        return dfs(1, 0) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        i, mod = 1, 10 ** 9 + 7\n",
    "        cand = []\n",
    "        acu = [0]\n",
    "        while True:\n",
    "            cur = i ** x\n",
    "            if cur > n: break\n",
    "            cand.append(cur)\n",
    "            acu.append(acu[-1] + cur)\n",
    "            i += 1\n",
    "        @cache\n",
    "        def dfs(i, n):\n",
    "            if n == 0: return 1\n",
    "            if n < 0 or i < 0 or acu[i+1] < n: return 0\n",
    "            return (dfs(i-1, n) + dfs(i-1, n-cand[i]))%mod\n",
    "        return dfs(len(cand)-1, n)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "        mod = int(1e9+7)\n",
    "        @cache\n",
    "        def dfs(n, m):\n",
    "            if n < 0 or m < 0:\n",
    "                return 0\n",
    "            if n == 0 and m == 0:\n",
    "                return 1\n",
    "            res = (dfs(n - pow(m, x), m - 1) + dfs(n, m - 1)) % mod\n",
    "            return res\n",
    "        def count_ways(n, x):\n",
    "            m = 1\n",
    "            while pow(m + 1, x) <= n:\n",
    "                m += 1\n",
    "            return dfs(n, m)\n",
    "        return count_ways(n, x)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfWays(self, n: int, x: int) -> int:\n",
    "      mod = 10 ** 9 + 7\n",
    "\n",
    "      @cache\n",
    "      def dfs(num, target):\n",
    "        if target == 0:\n",
    "          return 1\n",
    "        if num ** x > target:\n",
    "          return 0\n",
    "        res = dfs(num + 1, target - num ** x) % mod\n",
    "        res = (res + dfs(num + 1, target)) % mod\n",
    "        return res\n",
    "\n",
    "      return dfs(1, n)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
